package com.javabasic.algorithm.leetcode;

import org.junit.jupiter.api.Test;

import java.util.Objects;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2024/1/6 22:17
 */
public class InsertGreatestCommonDivisorsInLinkedList {


    @Test
    public void test() {
        System.out.println(gcd(12, 18));
        System.out.println(gcd(18, 12));
    }

    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }


    /**
     * 欧里几德算法+链表操作
     * 辗转相除法求解最大公约数
     *
     * @param head
     * @return {@link ListNode}
     */
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (Objects.isNull(head) || Objects.isNull(head.next)) {
            return head;
        }
        ListNode movePoint = head;
        int gcd;
        ListNode gcdNode;
        while (movePoint.next != null) {
            gcd = gcd(movePoint.val, movePoint.next.val);
            gcdNode = new ListNode(gcd);
            gcdNode.next = movePoint.next;
            movePoint.next = gcdNode;
            movePoint = gcdNode.next;
        }

        return head;
    }
}
